The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Network devices, such as network switches, routers, edge devices and the like, often employ lookup tables that store various information associated with packets processed by the network devices, and a network device performs lookups in the lookup tables for making various processing decisions during processing of packets by the network device. For example, lookup operations may be performed for packet classification, forwarding decisions, quality of service classifications, policy control list applications, and other processing operations generally performed by network devices. In general, a lookup for a packet is performed according to a key associated with or generated for the packet. The key is used to search a table, for example, and information relevant to the packet (e.g., forwarding information for the packet) is retrieved from an entry in the table identified by the key. Some lookup tables are implemented using content addressable memory (CAM). A CAM based table is a fully associative array that generally allows all keys provided to the table to be inserted into the table as long as the maximum number of table entries has not been exceeded. However, while a CAM table allows insertion of all keys provided to the table, CAM based tables generally are expensive in terms of area and power consumption, especially when large size lookup tables are employed.
An alternative implementation of a lookup table utilizes a hash based scheme in which a hash function is applied to a key to determine a location in the hash table at which the key and information associated with the key (e.g., forwarding information) are stored. While hash tables are generally smaller and more efficient compared to CAM implementations, hash tables exhibit inherent collisions when a hash function generates the same hashed values for two or more different keys provided to the hash function, and as a result, some keys provided to a hash table cannot be inserted into the hash table. Therefore, a lookup operation for some keys provided to a hash table will not produce a match. Thus, it is difficult to achieve exact match lookup performance when hash tables are employed. Various techniques, such as increasing hash table size or utilizing auxiliary search mechanisms to resolve hash collisions, have been employed to overcome the inherent deficiencies of conventional hash tables. However, such techniques are generally inefficient and can ultimately reduce desirability of using hash tables to perform exact match lookups.